This invention relates generally to efficient transfer of digital information among nodes. In particular, it is directed to a novel digital network in which digital information is exchanged among nodes in containers of any number of data units.
To date, communication networks have been primarily used for voice services and support limited data and computer services. In recognition of the predominance of voice traffic, a circuit switched channelized architecture evolved and was optimized for telephony. Data and computer communications access and transport have been provided as an overlay on this channelized infrastructure.
Although many data technologies have been developed, the advent and subsequent popularity of the Internet, coupled with its ability to support multiple services, including telephony, is changing the way users communicate and do business. Today, telecommunications networks are shifting from specialized networks toward multipurpose multi-functional networks.
The emerging data network must be able to grow to a much-higher capacity than the capacity of today""s voice and data networks. In addition to the huge-capacity requirement, the emerging networks must provide diverse and versatile services. The multiplicity of connection protocols, and the effort required for their interworking, inhibit the ability of the network to provide service diversity. The simplest network would be fully connected, allowing every networking device to have a physical connection to every other networking device. However, as the network size grows, this fully-meshed structure rapidly becomes impractical. Due to the spatial variation of traffic loads, and the typically large modular sizes of transport links, a fully-meshed network normally leads to underutilized transport facilities.
Currently, transport-capacity sharing is based on coarse-granularity, where point-to-point connections are defined as multiples of standard tributaries, such as OC3, OC12, etc. This renders tandem switchingxe2x80x94at a lower granularityxe2x80x94necessary to establish end-to-end connections with an acceptable quality-of-service (QOS) and an acceptable overall network efficiency. A low-connectivity network with excessive tandem switching may however lead to an uneconomical network, due to the increased number of hops between origin and destination and the cost of processing in intermediate nodes. Tandem switching in the multi-protocol environment is rather complicated, and several techniques have been proposed to reduce the processing at intermediate nodes by creating xe2x80x9cshort-cutsxe2x80x9d, see for example, an article in IEEE INFOCOM, 1996, pp. 1251-1260, xe2x80x9cFlowxe2x80x94Labelled IP: A Connectionless Approach to ATMxe2x80x9d by P. Newman et al. In addition, tandem switching adds variable delay and increases latency.
The multiplicity of communications protocols and the need for coexistence between new networks and legacy networks complicate the network planning function. In addition, QOS is difficult to realize in such a heterogeneous network. Currently, IP-based networks do not take the QOS into account, and one of the approaches to provide QOS assurance is to interworkxe2x80x94at a prohibitive costxe2x80x94with an underlying switch-based network, such as ATM networks. The complexity and fragility of such approaches are formidable impediments to network scaleability.
Traditional transport systems can offer a meshed network by providing direct interconnections between the networking devices. However, the connections would be based on channelized time division multiplexing, where the bandwidth allocated to a node-pair is fixed and dedicated to the node-pair. When the connection between two devices is inactive for some period of time, the transport bandwidth is still reserved so that it cannot be utilized by other active connections. Thus the networking device interfaces may not be as efficiently utilized as in the tandem approach which allows interconnections from many networking devices to share the interface to a given device.
U.S. Pat. No. 5,293,376, issued Mar. 8, 1994 (White), describes an upgradable telecommunication network which comprises a plurality of interconnected nodes or central offices, such as a SONET ring network. In its network, a unique controller enables a subscriber to change the central office or node in the network to which it is connected without changing the telephone number of the subscriber location.
U.S. Pat. No. 5,247,518, issued Sep. 21, 1993 (Takiyasu et al), teaches a high speed ring LAN system in which SONET subframes flow in a time-divisional n-multiplexed format. The respective node devices inserted in the transmission path have one or more ports to accommodate sub-LANs or public networks. Information is exchanged in units of a fixed-length container (packet) between a received SONET subframe and an asynchronous port, whereas information is exchanged in units of a byte between the SONET subframe and a synchronous port.
U.S. Pat. No. 5,406,401, issued Apr. 11, 1995 (Kremer) describes a technique of selective tributary switching in a bi-directional ring transmission system. The patent describes how selective switching in a bi-directional transmission system is used to realize selective tributary switching. A portion of bandwidth of a link that has been provisioned to be line-switched is governed by the set-up and take down procedures of full line-switching. The remaining bandwidth can be left unprotected but can be path-switched, because the line-switching functionality is combined with path-switching functionality in the same ring transmission system.
A fully-meshed network, as depicted in FIG. 1, is not scaleable to cover a large number of nodes, unless the link capacities are elastic and can be modified rapidly to follow the traffic-demand variation. With fixed capacities and fluctuating traffic demand, the transport utilization drops rapidly as the number of nodes increases. An elastic network, however, would allow all the connections to share a common pool of capacity through paths whose capacities are dynamically adjustable.
The envisaged network to be described herein has a high-connectivity structure. The basic requirements of such a network are simplicity, scalexe2x80x94ability, transport efficiency, the ability to accommodate existing legacy subnetworks, andxe2x80x94most importantlyxe2x80x94high reliability. There are several candidate topologies which, primarily, fall into two main categories: cross-connection and ring sharing.
Both cross-connection-based and ring-based networks can be configured to be fully meshed or almost fully meshed. A cross-connection-based network would normally have a lower connectivity than a ring-based network and is not discussed in this disclosure. A ring structure lends itself to fine capacity partitioning with relatively simple controls. Ring sharing can be achieved in several ways; for example by using ATM nodes and SONET rings, as depicted in FIG. 2. However, a flexible-transport layer as shown in FIG. 3 would achieve a more economical solution. A path of controlled variable capacity for each node pair is established in the network, thus creating a flexible fully-connected network. Each path may carry multiple traffic classes, and the capacity of the path can be dynamically shared among the classes at the container-packing stage. The network can accommodate a mixture of data, voice, and video traffic of both unicast and multicast nature. The multiclass service discipline is decided only at the originating and terminating nodes.
A pending U.S. patent application Ser. No. 08/755,431 filed on Nov. 21, 1996 for xe2x80x9cTransport Architecture and Network Elementsxe2x80x9d has inventors common to those of the present application and describes a ring structure with capacity partitioning. The invention described therein allows many networking devices to be interconnected with efficiently utilized interfaces, without incurring the cost and service degradation of a tandem device. A domain is defined where every networking device within the domain is connected to every other networking device within it with fixed or variable capacity. All the connections within the domain share a common pool of capacity, maximizing the utilization of the device interfaces. Since this new function is integrated into the transport network, the cost and service degradation associated with tandem networking devices is avoided. Various networking devices which use different protocols, such as ATM or IP, are accommodated by defining a container structure which carries digital information in its native form between them. The containers are carried on a digital facility with a defined bit rate that circulates on a ring or virtual ring past every networking device in the domain.
The present invention extends the concept of the meshed networking based on a ring configuration described in the above referenced patent application. The meshed network of the invention allows all the connections to share a common pool of capacity through links among nodes whose capacities are dynamically adjustable. Like the invention of the patent application referred to above, nodes provide data packaging into xe2x80x9ccontainersxe2x80x9d for transport and a ring exchanges data containers among its nodes but in the present invention, the containers may be of fixed or variable sizes. The invention calls for a service rate calculation for each source-destination node pair which is carried out by a centralized or distributed controller. Such controller either monitors the traffic or receives updated capacity-allocation requests from the nodes, and assigns an appropriate data rate at which each node can transmit to each destination. With lossless rings (traffic-wise), the quality of service is controlled solely by the source and destination nodes, without any interference from other data streams within the network. By reducing the complexity of the network core, an economical, reliable, and manageable network with feature-rich edge nodes can be realized.
In summary, a flexible programmable transport simplifies network management and extends the network capacity and network coverage by letting the end nodes control the QOS and end-to-end capacity allocation. Rather than forcing the network to cope with multiple protocols, node-pairs can communicate directly through adaptive end-to-end links. Thus, interoperability is replaced by protocol disengagement. The flexible capacity allocation can be realized in frame-based or container-based schemes. This technique is particularly attractive because of its inherent compatibility with the North-American fiber-network topology.
Other U. S. pending patent applications Ser. No. 08/834,974 filed on Apr. 7, 1997 for xe2x80x9cParallel Service-Rate Controllers in ATM Switchesxe2x80x9d, Serial No. 08/827,882 filed on Apr. 7, 1997 for xe2x80x9cLarge-scale Serial Service Rate Regulators for ATM Switchingxe2x80x9d and Ser. No. 08/985,297 filed on Dec. 4, 1997 for xe2x80x9cATM Service Scheduler using Reverse-Binary Scattering and Time-space Mappingxe2x80x9d all have an inventor common to the present application. These pending applications describe in detail the rate controlling and scheduling techniques of a shared medium which are applicable to the present invention.
It is an object of the invention to provide a flexible programmable transport network which realizes a fully meshed configuration, simple network management and easy capacity scaleability and yet which is compatible with current transport networks and possibly with future all-optical networks.
It is a further object of the invention to provide a fully meshed network in which the end nodes in each pair control the QOS of the traffic between them according to end-to-end capacity allocations.
It is yet another object of the invention to provide a ring network in which, node-pairs can communicate directly through adaptive end-to-end links whose capacity is dynamically adjustable.
It is still an object of the invention to provide a fully meshed network in which traffic is exchanged among the nodes in containers of any desired number of data units.
It is an additional object of the invention to provide a fully meshed network in a ring configuration in which container scheduling is provided, sharing bandwidth at the topological level.
It is a further object of the invention to provide a fully meshed network in ring configuration in which centralized control and distributed control schemes can coexist.
Briefly stated, in accordance with one aspect, the invention is directed to a communication network for transporting digital traffic among a plurality of nodes in a fully meshed logical configuration. The network comprises a dual transport ring for transporting digital traffic in opposite directions, the digital traffic consisting of containers of digital signal, each container containing any number of data units and being destined to one or more nodes among the plurality of nodes. The network further includes the plurality of nodes located on the dual transport ring, each node extracting from the dual transport ring containers destined to it and inserting thereto containers destined to any of the remaining nodes and each node controlling a rate at which it inserts to the dual transport ring the amount of data in the containers destined to any of the remaining nodes.
According to another aspect, the invention is directed to a node in a communications network which transports digital traffic among a plurality of nodes via a dual transport ring in a fully meshed logical configuration, the digital traffic consisting of containers of any number of data units. The node comprises two ring buffers for storing traffic in the dual transport ring coming into the node and an add buffer for storing containers to be inserted into the dual transport ring. The node further includes a drop buffer for storing containers extracted at the node from the dual transport ring and a rate scheduler for scheduling insertion of containers into the dual transport ring in accordance with an allowed rate approved by the communication network.
In accordance with another aspect, the invention is directed to a method of transporting digital traffic among a plurality of nodes located on a dual transport ring in a fully meshed logical configuration. The method comprises steps of storing a plurality of data streams in a plurality of add buffers according to their destinations and acquiring an allowed data rate at which each data stream is to be inserted to the dual transport ring. The method further includes steps of extracting a properly addressed data stream from the dual transport ring, storing it in a drop buffer and inserting a plurality of data streams into the dual transport ring at locations properly assigned to their destinations.
In accordance with a yet another aspect, the invention is directed to a method of scheduling digital data at a node in a telecommunications network in which the network is formed by a ring transport medium having a plurality of nodes and the digital data comprises a plurality of data streams. The method comprises steps of storing the plurality of data streams respectively in a plurality of storage locations and calculating a parameter indicative of an accumulated rate of the data streams stored in each storage location. The method includes further steps of declaring each data stream eligible for transport when the parameter exceeds an allowed data rate of said data stream and transporting into the ring transport medium each eligible data stream in accordance with a predetermined criterion.